#include <bits/stdc++.h>
using namespace std;

class Test{
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target){
		// 1. sorted
		vector<vector<int>> result;
		sort(nums.begin(),nums.end());
		for(int k = 0;k < nums.size();k++){
			// 2. 剪枝
			if(nums[k] >= 0 && nums[k] > target){
				break;
			}
			// 3. 去重
			if(k > 0 && nums[k] == nums[k-1]){
				continue;
			}
			for(int i = k + 1; i<nums.size();i++){
				// 4. i的剪枝
				if(nums[i] + nums[k] >= 0 && nums[i] + nums[k] > target){
					break;
				}
				// 5. i的去重
				if(i > k+1 && nums[i] == nums[i-1]){
					continue;
				}
				int left = i+1;
				int right = nums.size()-1;
				while(left < right){
					int t = nums[k] + nums[i] + nums[left] + nums[right];
					if(t > target){
						right--;
					}else if(t < target){
						left++;
					}else{
						result.push_back({nums[k],nums[i],nums[left],nums[right]});
						while(left < right && nums[left] == nums[left + 1]) left++;
						while(left < right && nums[right] == nums[right-1]) right--;
						left++;
						right--;
					}
				}
			}
			return result;
		}
	}
};
int main(){
	
	return 0;
}
